#include "stdafx.h"
#include "BucketSort.h"
#include <iostream>
#include <list>

using namespace std;

int BucketSort::GetBucket(int num){
	if(num < 0) return 0;
	if(num >= 100) return 9;
	return num / 10;
}

void BucketSort::Sort(ArrayPtr Arr, const int size){
	typedef list<int> * Bucket;
	Bucket buckets = new list<int>[10]();
	for(int i = 0; i < size; ++i){
		int bucketNum = GetBucket(Arr[i]);
		buckets[bucketNum].push_back(Arr[i]);
		buckets[bucketNum].sort();
	}
	int cnt = 0 ;
	for(int i = 0; i < 10 ; ++i){
		for(;;){
			if(buckets[i].empty()) break;
			Arr[cnt++] = buckets[i].front();
			buckets[i].pop_front();
		}
	}
	delete [] buckets;
}